#include "BTreeNode.h"
#include "Bruinbase.h"
#include <stdio.h>
#include <string.h>
using namespace std;


/**
 * Move pointer to the beginning of the buffer;
 */

void BTLeafNode::resetPtr() {
	buffer_ptr = (l_struct*) (buffer + sizeof(int));
}

BTLeafNode::BTLeafNode() {
	memset(buffer, 0, sizeof(buffer));
	resetPtr();
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Update total keys
 */
void BTLeafNode::updateTotalKeys(int count) {
	memcpy(buffer, &count, sizeof(int));
}
		
/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	// read first four bytes;
	int count;
	memcpy(&count, buffer, sizeof(int));
	return count;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int total_keys = getKeyCount();

	if(total_keys == MAX_KEY_PER_NODE) {
		return RC_NODE_FULL;
	}

	resetPtr();
	int index = 0;

	while (key > buffer_ptr->key && (index != total_keys)) {
		++index;
		++buffer_ptr;
	}

	// shift all elements to the right if we don't insert at the end of the buffer
	if (index != total_keys) shift_r(index);

	// insert key & rid
	buffer_ptr->rid = rid;
	buffer_ptr->key = key;

	// update the total keys
	updateTotalKeys(total_keys + 1);

	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	RC rc;

	if (!sibling.getKeyCount())
		return RC_INVALID_NODE;


	int total_keys = getKeyCount();

	// reset pointer
	resetPtr();

	// find the spot where the new key should be inserted
	int key_spot = 0;
	while (key > buffer_ptr->key || (key_spot != total_keys)) {
		++key_spot;
		++buffer_ptr;
	}


	// middle of the node
	resetPtr();
	int middle_spot = total_keys / 2;
	buffer_ptr += middle_spot;
	int insert_to_sibling = 0;

	if (key_spot > middle_spot) {
		++middle_spot;
		insert_to_sibling = 1;
	}


	// copy right half to sibling
	for (int i = middle_spot; i < total_keys; ++i, ++buffer_ptr) {
		sibling.insert(buffer_ptr->key, buffer_ptr->rid);
	}

	if (!insert_to_sibling) {
		insert(key, rid);
	} else
		sibling.insert(key, rid);

	sibling.resetPtr();
	int sib_key;
	RecordId sib_rid;
	if ((rc = sibling.readEntry(0, sib_key, sib_rid)) < 0) return rc;

	siblingKey = sib_key;

	// update number of keys
	updateTotalKeys(middle_spot);

	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	resetPtr();
	int total_keys = getKeyCount();
	int i;
	for (i = 0; i < total_keys; ++i, ++buffer_ptr) {
		if (buffer_ptr->key >= searchKey) {
			eid = i;
			break;
		}
	}

	if (i >= total_keys) {
		return RC_NO_SUCH_RECORD;
	}

	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int total_keys = getKeyCount();

	if (eid < 0 || eid >= total_keys)
		return RC_NO_SUCH_RECORD;

	resetPtr();
	buffer_ptr += eid;

	key = buffer_ptr->key;
	rid = buffer_ptr->rid;

	return 0;
}


/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	int next_pageid;
	memcpy(&next_pageid, buffer + (PageFile::PAGE_SIZE - sizeof(int)), sizeof(int));

	return next_pageid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	memset(buffer + (PageFile::PAGE_SIZE - sizeof(int)), pid, sizeof(int));

	return 0;
}

void BTLeafNode::shift_r(int index){
	memcpy(buffer_ptr + 1, buffer_ptr, (getKeyCount() - index) * SLOT_SIZE);
}


/////////// NON LEAF /////////////
/**
 * Move pointer to the beginning of the buffer;
 */

void BTNonLeafNode::resetPtr() {
	buffer_ptr = (nl_struct*) (buffer + sizeof(int) * 2);
}

BTNonLeafNode::BTNonLeafNode() {
	memset(buffer, 0, sizeof(buffer));
	resetPtr();
}

void BTNonLeafNode::updateTotalKeys(int count) {
	memcpy(buffer, &count, sizeof(int));
}

void BTNonLeafNode::shift_r(int index){
	memcpy(buffer_ptr + 1, buffer_ptr, (getKeyCount() - index) * SLOT_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	RC rc;
	if ((rc = pf.read(pid, buffer)) < 0) return rc;
	resetPtr();
	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	// read first four bytes;
	int count;
	memcpy(&count, buffer, sizeof(int));
	return count;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int total_keys = getKeyCount();

	if(total_keys == MAX_KEY_PER_NODE) {
		return RC_NODE_FULL;
	}

	resetPtr();
	int index = 0;

	while (key > buffer_ptr->key || (index != total_keys)) {
		++index;
		++buffer_ptr;
	}

	// shift all elements to the right if we don't insert at the end of the buffer
	if (index != total_keys) shift_r(index);

	// insert key & pid
	buffer_ptr->key = key;
	buffer_ptr->pid = pid;

	// update the total keys
	updateTotalKeys(total_keys + 1);

	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	RC rc;
	
	if (!sibling.getKeyCount())
		return RC_INVALID_NODE;

	int total_keys = getKeyCount();

	// reset pointer
	resetPtr();

	// find the spot where the new key should be inserted
	int key_spot = 0;
	while (key > buffer_ptr->key || (key_spot != total_keys)) {
		++key_spot;
		++buffer_ptr;
	}


	// middle of the node
	resetPtr();
	int middle_spot = total_keys / 2;
	buffer_ptr += middle_spot;

	if (middle_spot == key_spot) {
		midKey = key;
	} else if (key_spot < middle_spot) {
		if (total_keys % 2 == 0) {
			midKey = (buffer_ptr - 1)->key;

			// update the number of keys first to make it non-full
			updateTotalKeys(middle_spot - 1);
			insert(key, pid);
		} else {
			midKey = buffer_ptr->key;
			++buffer_ptr;
			sibling.insert(key, pid);
		}
	} else {
		midKey = buffer_ptr->key;
		++buffer_ptr;
		sibling.insert(key, pid);
	}

	// copy right half to sibling
	for (int i = middle_spot; i < total_keys; ++i, ++buffer_ptr) {
		sibling.insert(buffer_ptr->key, buffer_ptr->pid);
	}

	// update number of keys
	updateTotalKeys(middle_spot);

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	resetPtr();
	int total_keys = getKeyCount();
	int index = 1;

	while (searchKey > buffer_ptr->key || (index < total_keys)) {
		++index;
		++buffer_ptr;
	}
	if(buffer_ptr->key >= searchKey) 
		pid = buffer_ptr->pid;  // >=  goes to the right
	else 
		pid = (--buffer_ptr)->pid; // <  goes to the left

	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	resetPtr();

	buffer_ptr->key = key;
	buffer_ptr->pid = pid2;
	(--buffer_ptr)->pid = pid1;

	return 0;
}

/**
 * Simple return the left sibling's pid of the current node
 */
 RC BTNonLeafNode::getLeftSiblingPid(int &pid) {
	 resetPtr();
	 pid = (--buffer_ptr)->pid;
	 return 0;
 }
